package com.tgy.algorithm.base._二叉树;

import java.util.Stack;

public class _二叉树的遍历_01 {

    public static BiTreeNode getBiTreeNode() {

        /**
         *          1
         *      2         3
         *   4    5     6     7
         */
        BiTreeNode header = new BiTreeNode(1);
        header.left = new BiTreeNode(2);
        header.right = new BiTreeNode(3);
        header.left.left = new BiTreeNode(4);
        header.left.right = new BiTreeNode(5);
        header.right.left = new BiTreeNode(6);
        header.right.right = new BiTreeNode(7);
        return header;
    }


    public static void biTreeInOrder(BiTreeNode root) {
        if (root == null) {
            return;
        }

        Stack<BiTreeNode> stack = new Stack<>();
        BiTreeNode node = root;
        while (!stack.isEmpty() || node != null){
            if (node != null) {
                stack.push(node);
                node = node.left;
            }else {
                BiTreeNode newNode = stack.pop();
                System.out.println(newNode.val);
                node = newNode.right;
            }
        }
    }

    public static void biTreePostOrder(BiTreeNode root) {
        if (root == null) {
            return;
        }

        /**
         *          1
         *      2         3
         *   4    5     6     7
         */
        Stack<BiTreeNode> stack = new Stack<>();
        stack.push(root);
        BiTreeNode preNode = root;
        while (!stack.isEmpty()) {
            BiTreeNode node = stack.peek();
            if (node.left != null && node.left != preNode
                    && node.right != null && node.right != preNode) {
                while (node.left != null) {
                    stack.push(node.left);
                    node = node.left;
                }
            }else if (node.left == preNode) {
                if (node.right != null) {
                    stack.push(node.right);
                }
            }else {
               BiTreeNode newNode = stack.pop();
               System.out.println(newNode.val);
               preNode = newNode;
            }
        }
    }

    public static void main(String[] args) {
//        biTreeInOrder(getBiTreeNode());
        biTreePostOrder(getBiTreeNode());
    }

}
